package leetcode.all;

public class Solution81 {
    public boolean search(int[] nums, int target) {
        int l = 0, r = nums.length-1, mid = 0;
        while (l<=r){
            mid = (l+r)>>1;
            if(nums[mid]==target) return true;
            if(nums[mid]>nums[r]){ //mid在左支[l,mid]有序
                if(target>=nums[l]&&target<=nums[mid]){
                    r = mid-1;
                }else {
                    l = mid+1;
                }
            }else if(nums[mid]<nums[r]) { //mid在右支[mid,r]有序
                if (target >= nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }else { //nums[mid]==nums[r]
                // 无法直接让l=mid+1或r=mid-1，因为这样可能漏掉一些没搜索到的num
                // 但已知nums[r]!=target，所以可以收缩右边界一步
                r = r - 1;
            }
        }
        return false;
    }
}
